package training;

import java.util.Stack;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_6_6_Training {
    //使用机器人打印字典序最小的字符串
    public String robotWithString(String s) {
        int[] map = new int[26];
        for (int i = 0; i < s.length(); i++) {
            map[s.charAt(i) - 'a']++;
        }
        int len = s.length();
        StringBuilder sb = new StringBuilder();
        Stack<Character> st = new Stack<>();
        int i = 0;
        while (len != 0) {
            char min = 'a';
            while (min != 'z' && map[min - 'a'] == 0) {
                min++;
            }
            if (!st.isEmpty() && st.peek() <= min) {
                sb.append(st.pop());
                continue;
            }
            for (; i < s.length(); i++) {
                if (s.charAt(i) == min) {
                    sb.append(min);
                    map[min - 'a']--;
                    len--;
                    i++;
                    break;
                }
                st.add(s.charAt(i));
                map[s.charAt(i) - 'a']--;
                len--;
            }
        }
        while (!st.isEmpty()) {
            sb.append(st.pop());
        }
        return sb.toString();
    }
}
